Search for: All records

A $(β,δ,Δ)$-padded decomposition of an edge-weighted graph $G = (V,E,w)$ is a stochastic decomposition into clusters of diameter at most $$Δ$$ such that for every vertex $$v\in V$$, the probability that $$\rm{ball}_G(v,γΔ)$$ is entirely contained in the cluster containing $$v$$ is at least $$e^{-βγ}$$ for every $$γ\in [0,δ]$$. Padded decompositions have been studied for decades and have found numerous applications, including metric embedding, multicommodity flow-cut gap, multicut, and zero extension problems, to name a few. In these applications, parameter $$β$$, called the padding parameter, is the most important parameter since it decides either the distortion or the approximation ratios. For general graphs with $$n$$ vertices, $$β= Θ(\log n)$$. Klein, Plotkin, and Rao showed that $$K_r$$-minor-free graphs have padding parameter $β= O(r^3)$, which is a significant improvement over general graphs when $$r$$ is a constant. A long-standing conjecture is to construct a padded decomposition for $$K_r$$-minor-free graphs with padding parameter $$β= O(\log r)$$. Despite decades of research, the best-known result is $β= O(r)$, even for graphs with treewidth at most $$r$$. In this work, we make significant progress toward the aforementioned conjecture by showing that graphs with treewidth $$\rm{tw}$$ admit a padded decomposition with padding parameter $$O(\log \rm{tw})$$, which is tight. As corollaries, we obtain an exponential improvement in dependency on treewidth in a host of algorithmic applications: $$O(\sqrt{ \log n \cdot \log(\rm{tw})})$$ flow-cut gap, max flow-min multicut ratio of $$O(\log(\rm{tw}))$$, an $$O(\log(\rm{tw}))$$ approximation for the 0-extension problem, an $$\ell^{O(\log n)}_\infty$$ embedding with distortion $$O(\log \rm{tw})$$, and an $$O(\log \rm{tw})$$ bound for integrality gap for the uniform sparsest cut. 39 pages. This is the TheoretiCS journal version 

When training node embedding models to represent large directed graphs (digraphs), it is impossible to observe all entries of the adjacency matrix during training. As a consequence most methods employ sampling. For very large digraphs, however, this means many (most) entries may be unobserved during training. In general, observing every entry would be necessary to uniquely identify a graph, however if we know the graph has a certain property some entries can be omitted - for example, only half the entries would be required for a symmetric graph. In this work, we develop a novel framework to identify a subset of entries required to uniquely distinguish a graph among all transitively-closed DAGs. We give an explicit algorithm to compute the provably minimal set of entries, and demonstrate empirically that one can train node embedding models with greater efficiency and performance, provided the energy function has an appropriate inductive bias. We achieve robust performance on synthetic hierarchies and a larger real-world taxonomy, observing improved convergence rates in a resource-constrained setting while reducing the set of training examples by as much as 99%.